{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum XOR of Two Non-Overlapping Subtrees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #graph #trie"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #图 #字典树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxXor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个不重叠子树的最大异或值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个无向树，有 <code>n</code> 个节点，节点标记为从 <code>0</code> 到 <code>n - 1</code>。给定整数 <code>n</code> 和一个长度为 <code>n - 1</code> 的 2 维整数数组 <code>edges</code>，其中 <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 表示在树中的节点 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 之间有一条边。树的根节点是标记为 <code>0</code> 的节点。</p>\n",
    "\n",
    "<p data-group=\"1-1\">每个节点都有一个相关联的 <strong>值</strong>。给定一个长度为 n 的数组 <code>values</code>，其中 <code>values[i]</code> 是第 <code>i</code> 个节点的&nbsp;<strong>值</strong>。</p>\n",
    "\n",
    "<p>选择任意两个&nbsp;<strong>不重叠&nbsp;</strong>的子树。你的&nbsp;<strong>分数&nbsp;</strong>是这些子树中值的和的逐位异或。</p>\n",
    "\n",
    "<p>返回<em>你能达到的最大分数</em>。<em>如果不可能找到两个不重叠的子树</em>，则返回 <code>0</code>。</p>\n",
    "\n",
    "<p><strong>注意</strong>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点的&nbsp;<strong>子树&nbsp;</strong>是由该节点及其所有子节点组成的树。</li>\n",
    "\t<li>如果两个子树不共享&nbsp;<strong>任何公共&nbsp;</strong>节点，则它们是&nbsp;<strong>不重叠&nbsp;</strong>的。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/22/treemaxxor.png\" style=\"width: 346px; height: 249px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 6, edges = [[0,1],[0,2],[1,3],[1,4],[2,5]], values = [2,8,3,6,2,5]\n",
    "<strong>输出:</strong> 24\n",
    "<strong>解释:</strong> 节点 1 的子树的和值为 16，而节点 2 的子树的和值为 8，因此选择这些节点将得到 16 XOR 8 = 24 的分数。可以证明，这是我们能得到的最大可能分数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/22/tree3drawio.png\" style=\"width: 240px; height: 261px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 3, edges = [[0,1],[1,2]], values = [4,6,1]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong> 不可能选择两个不重叠的子树，所以我们只返回 0。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>edges.length == n - 1</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>values.length == n</code></li>\n",
    "\t<li><code>1 &lt;= values[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li>保证 <code>edges</code> 代表一个有效的树。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-xor-of-two-non-overlapping-subtrees](https://leetcode.cn/problems/maximum-xor-of-two-non-overlapping-subtrees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-xor-of-two-non-overlapping-subtrees](https://leetcode.cn/problems/maximum-xor-of-two-non-overlapping-subtrees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n[[0,1],[0,2],[1,3],[1,4],[2,5]]\\n[2,8,3,6,2,5]', '3\\n[[0,1],[1,2]]\\n[4,6,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxXor(self, n: int, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        A = [0]*n\n",
    "        def dfs(u,f):\n",
    "            A[u] = values[u]\n",
    "            for v in g[u]:\n",
    "                if v!=f:\n",
    "                    dfs(v,u)\n",
    "                    A[u] += A[v]\n",
    "        dfs(0,-1)\n",
    "        L = A[0].bit_length()\n",
    "        T = [set() for _ in range(L)]\n",
    "        self.res = 0\n",
    "        def dfs(u,f):\n",
    "            x, y = A[u], 0\n",
    "            for j in range(L-1,-1,-1):\n",
    "                y *= 2\n",
    "                y += (y+1)^(x>>j) in T[j]\n",
    "            self.res = max(self.res,y)\n",
    "            for v in g[u]:\n",
    "                if v!=f:\n",
    "                    dfs(v,u)\n",
    "            for j in range(L):\n",
    "                T[j].add(x>>j)\n",
    "        dfs(0,-1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxXor(self, n: int, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        A = [0]*n\n",
    "        def dfs(u,f):\n",
    "            A[u] = sum(dfs(v,u) for v in g[u] if v!=f)+values[u]\n",
    "            return A[u]\n",
    "        dfs(0,-1)\n",
    "        L = A[0].bit_length()\n",
    "        T = [set() for _ in range(L)]\n",
    "        self.res = 0\n",
    "        def dfs(u,f):\n",
    "            x, y = A[u], 0\n",
    "            for j in range(L-1,-1,-1):\n",
    "                y *= 2\n",
    "                y += (y+1)^(x>>j) in T[j]\n",
    "            self.res = max(self.res,y)\n",
    "            for v in g[u]:\n",
    "                if v!=f:\n",
    "                    dfs(v,u)\n",
    "            for j in range(L):\n",
    "                T[j].add(x>>j)\n",
    "        dfs(0,-1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxXor(self, n: int, edges: list[list[int]], values: list[int]) -> int:\n",
    "        # 构建邻接表\n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        \n",
    "        # 使用 DFS 计算每个节点的子树值总和\n",
    "        A = [0] * n\n",
    "        def dfs(u, f):\n",
    "            A[u] = sum(dfs(v, u) for v in g[u] if v != f) + values[u]\n",
    "            return A[u]\n",
    "        dfs(0, -1)\n",
    "        \n",
    "        # 使用位操作来计算最大逐位异或值\n",
    "        L = A[0].bit_length()\n",
    "        T = [set() for _ in range(L)]\n",
    "        self.res = 0\n",
    "        \n",
    "        def dfs(u, f):\n",
    "            x, y = A[u], 0\n",
    "            for j in range(L - 1, -1, -1):\n",
    "                y *= 2\n",
    "                y += (y + 1) ^ (x >> j) in T[j]\n",
    "            self.res = max(self.res, y)\n",
    "            for v in g[u]:\n",
    "                if v != f:\n",
    "                    dfs(v, u)\n",
    "            for j in range(L):\n",
    "                T[j].add(x >> j)\n",
    "                \n",
    "        dfs(0, -1)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxXor(self, n: int, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        A = [0]*n\n",
    "        def dfs(u,f):\n",
    "            A[u] = sum(dfs(v,u) for v in g[u] if v!=f)+values[u]\n",
    "            return A[u]\n",
    "        dfs(0,-1)\n",
    "        L = A[0].bit_length()\n",
    "        T = [set() for _ in range(L)]\n",
    "        self.res = 0\n",
    "        def dfs(u,f):\n",
    "            x, y = A[u], 0\n",
    "            for j in range(L-1,-1,-1):\n",
    "                y *= 2\n",
    "                y += (y+1)^(x>>j) in T[j]\n",
    "            self.res = max(self.res,y)\n",
    "            for v in g[u]:\n",
    "                if v!=f:\n",
    "                    dfs(v,u)\n",
    "            for j in range(L):\n",
    "                T[j].add(x>>j)\n",
    "        dfs(0,-1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    __slots__ = 'children', 'cnt'\n",
    "\n",
    "    def __init__(self):\n",
    "        self.children = [None, None]\n",
    "        self.cnt = 0  # 子树大小\n",
    "\n",
    "\n",
    "class Trie:\n",
    "    HIGH_BIT = 19\n",
    "\n",
    "    def __init__(self):\n",
    "        self.root = Node()\n",
    "\n",
    "    # 添加 val\n",
    "    def insert(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            if cur.children[bit] is None:\n",
    "                cur.children[bit] = Node()\n",
    "            cur = cur.children[bit]\n",
    "            cur.cnt += 1  # 维护子树大小\n",
    "        return cur\n",
    "\n",
    "    # 删除 val，但不删除节点\n",
    "    # 要求 val 必须在 trie 中\n",
    "    def remove(self, val: int) -> None:\n",
    "        cur = self.root\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            cur = cur.children[(val >> i) & 1]\n",
    "            cur.cnt -= 1  # 维护子树大小\n",
    "        return cur\n",
    "\n",
    "    # 返回 val 与 trie 中一个元素的最大异或和\n",
    "    # 要求 trie 中至少有一个元素\n",
    "    def max_xor(self, val: int) -> int:\n",
    "        cur = self.root\n",
    "        if cur.children == [None, None]:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        for i in range(Trie.HIGH_BIT, -1, -1):\n",
    "            bit = (val >> i) & 1\n",
    "            # 如果 cur.children[bit^1].cnt == 0，视作空节点\n",
    "            if cur.children[bit ^ 1] and cur.children[bit ^ 1].cnt:\n",
    "                ans |= 1 << i\n",
    "                bit ^= 1\n",
    "            cur = cur.children[bit]\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxXor(self, n: int, edges: List[List[int]], values: List[int]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "\n",
    "        s = [0] * n\n",
    "\n",
    "        def dfs(node, fa):\n",
    "            res = values[node]\n",
    "            for nxt in g[node]:\n",
    "                if nxt != fa:\n",
    "                    res += dfs(nxt, node)\n",
    "            s[node] = res\n",
    "            return res\n",
    "\n",
    "        dfs(0, -1)\n",
    "\n",
    "        Trie.HIGH_BIT = s[0].bit_length() - 1\n",
    "        tree = Trie()\n",
    "        ans = 0\n",
    "\n",
    "        def f(node, fa):\n",
    "            nonlocal ans\n",
    "            tmp = tree.max_xor(s[node])\n",
    "            if tmp > ans:\n",
    "                ans = tmp\n",
    "            for nxt in g[node]:\n",
    "                if nxt != fa:\n",
    "                    f(nxt, node)\n",
    "            tree.insert(s[node])\n",
    "\n",
    "        f(0, -1)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
